package com.leetcode.algorithm.y18.m05;

import java.util.HashMap;

public class FasterSolution05 {
	
	/**
	 * 1.两数之和 
	 * 给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。 
	 * 你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。 
	 * 示例:
	 * 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9
	 * 所以返回 [0, 1]
	 * @param nums
	 * @param target
	 * @return
	 */
	public int[] twoSum(int[] nums, int target) {
		int[] index = new int[] { 0, 1 };
		HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();

		for (int i = 0; i < nums.length; i++) {
			if (hm.containsKey(target - nums[i])) {
				index[1] = i;
				index[0] = hm.get(target - nums[i]);
				return index;
			} else {
				hm.put(nums[i], i);
			}
		}
		return index;
	}

	
	// 二进制相关
	// 异或运算(同0异1) x ^ 0 = x; x^0bffffffff = x的反码
	/**
	 * 461. 汉明距离
	 *	两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
	 *	给出两个整数 x 和 y，计算它们之间的汉明距离。
	 *
	 *	注意：
	 *	0 ≤ x, y < 2的31次方.
	 *	示例:
	 *	输入: x = 1, y = 4
	 *	输出: 2
	 *	解释:
	 *	1   (0 0 0 1)
	 *	4   (0 1 0 0)
	 *	       ↑   ↑
	 *	上面的箭头指出了对应二进制位不同的位置。
	 * @param x
	 * @param y
	 * @return
	 */
	public int hammingDistance(int x, int y) {
		int hamming = x ^ y; // 异或运算(同0异1)
		int cnt = 0;
		while (hamming > 0) {
			hamming = hamming & (hamming - 1); // 很奇妙地计算出hamming的二进制表示中1的个数
			cnt++;
		}
		return cnt;
	}
	
	/**
	 * 136. 只出现一次的数字 
	 * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
	 * 
	 * 说明：
	 * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
	 * 
	 * 示例 1:
	 * 输入: [2,2,1] 
	 * 输出: 1 
	 * 
	 * 示例 2:
	 * 输入: [4,1,2,1,2] 
	 * 输出: 4
	 * 
	 * @param nums
	 * @return
	 */
	public int singleNumber(int[] nums) {
		int number = 0;
		for (int i = 0; i < nums.length; i++) {
			number ^= nums[i];
		}
		return number;
	}
	
    /**
	 * 190. 颠倒二进制位 
	 * 颠倒给定的 32 位无符号整数的二进制位。
	 * 
	 * 示例:
	 * 输入: 43261596 
	 * 输出: 964176192 
	 * 解释: 43261596 的二进制表示形式为  00000010100101000001111010011100 ， 
	 * 返回 964176192，其二进制表示形式为 00111001011110000010100101000000 。 
	 * 
	 * 进阶: 
	 * 如果多次调用这个函数，你将如何优化你的算法？
	 * 
	 * @param n
	 * @return
	 */
	public int reverseBits(int n) {
		int result = 0;
		for (int i = 0; i < 32; i++) {
			result = result << 1;
			result ^= (n & 1);	//n & 1获取n的最后一位
			n = n >>> 1;
		}
		return result;
	}
}